/**
 * 
 * 两个链表的第一个公共结点
 * 
 * 描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： 
n
≤
1000
n≤1000
要求：空间复杂度 
O
(
1
)
O(1)，时间复杂度 
O
(
n
)
O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
 */
public class 两个链表的第一个公共结点 {
    
    public static void main(String[] args) {
        
        // 链表 A：1->2->3->4->5->6->7
        ListNode nodeA1 = new ListNode(1);
        ListNode nodeA2 = new ListNode(2);
        ListNode nodeA3 = new ListNode(3);
        ListNode nodeA4 = new ListNode(4);
        ListNode nodeA5 = new ListNode(5);
        ListNode nodeA6 = new ListNode(6);
        ListNode nodeA7 = new ListNode(7);
        nodeA1.next = nodeA2;
        nodeA2.next = nodeA3;
        nodeA3.next = nodeA4;
        nodeA4.next = nodeA5;
        nodeA5.next = nodeA6;
        nodeA6.next = nodeA7;

        // 链表 B：8->9->4->5->6->7
        ListNode nodeB1 = new ListNode(8);
        ListNode nodeB2 = new ListNode(9);
        nodeB1.next = nodeB2;
        nodeB2.next = nodeA4;

        ListNode commonNode = FindFirstCommonNode(nodeA1, nodeB1);
        if (commonNode!= null) {
            System.out.println(commonNode.toString());
        } else {
            System.out.println("两个链表没有公共节点");
        }
    }

    private static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 

        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode pA = pHead1;
        ListNode pB = pHead2;
        while (pA!= pB) {
            pA = pA == null? pHead2 : pA.next;
            pB = pB == null? pHead1 : pB.next;
        }
        return pA;
    }
}
